The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] reed-solomon code(45hit)

1-20hit(45hit)

  • Variable-Length Orthogonal Codes over Finite Fields Realizing Data Multiplexing and Error Correction Coding Simultaneously

    Shoichiro YAMASAKI  Tomoko K. MATSUSHIMA  Kyohei ONO  Hirokazu TANAKA  

     
    PAPER-Coding Theory and Techniques

      Pubricized:
    2023/09/26
      Vol:
    E107-A No:3
      Page(s):
    373-383

    The present study proposes a scheme in which variable-length orthogonal codes generated by combining inverse discrete Fourier transform matrices over a finite field multiplex user data into a multiplexed sequence and its sequence forms one or a plural number of codewords for Reed-Solomon coding. The proposed scheme realizes data multiplexing, error correction coding, and multi-rate transmitting at the same time. This study also shows a design example and its performance analysis of the proposed scheme.

  • Optimal (r, δ)-Locally Repairable Codes from Reed-Solomon Codes

    Lin-Zhi SHEN  Yu-Jie WANG  

     
    LETTER-Coding Theory

      Pubricized:
    2023/05/30
      Vol:
    E106-A No:12
      Page(s):
    1589-1592

    For an [n, k, d] (r, δ)-locally repairable codes ((r, δ)-LRCs), its minimum distance d satisfies the Singleton-like bound. The construction of optimal (r, δ)-LRC, attaining this Singleton-like bound, is an important research problem in recent years for thier applications in distributed storage systems. In this letter, we use Reed-Solomon codes to construct two classes of optimal (r, δ)-LRCs. The optimal LRCs are given by the evaluations of multiple polynomials of degree at most r - 1 at some points in Fq. The first class gives the [(r + δ - 1)t, rt - s, δ + s] optimal (r, δ)-LRC over Fq provided that r + δ + s - 1≤q, s≤δ, s

  • Distributed Transmission for Secure Wireless Links Based on a Secret-Sharing Method

    Masaaki YAMANAKA  ShenCong WEI  Jingbo ZOU  Shuichi OHNO  Shinichi MIYAMOTO  Seiichi SAMPEI  

     
    PAPER-Wireless Communication Technologies

      Pubricized:
    2019/06/17
      Vol:
    E102-B No:12
      Page(s):
    2286-2296

    This paper proposes a secure distributed transmission method that establishes multiple transmission routes in space to a destination. In the method, the transmitted information is divided into pieces of information by a secret-sharing method, and the generated pieces are separately transmitted to the destination through different transmission routes using individually-controlled antenna directivities. As the secret-sharing method can divide the transmitted information into pieces in such a manner that nothing about the original information is revealed unless all the divided pieces are obtained, the secrecy of the transmitted information is greatly improved from an information-theoretic basis. However, one problem is that it does not perform well in the vicinity around the receiver. This is due to the characteristics of distributed transmission that all distributed pieces of information must eventually gather at the destination; an eavesdropper can obtain the necessary pieces to reconstruct the original information. Then, this paper expands the distributed transmission method into a two-way communication scheme. By adopting the distributed transmission in both communication directions, a secure link can be provided as a feedback channel to enhance the secrecy of the transmitted information. The generation of the shared pieces of information is given with signal forms, and the secrecy of the proposed method is evaluated based on the signal transmission error rates as determined by computer simulation.

  • New Asymptotically Optimal Optical Orthogonal Signature Pattern Codes from Cyclic Codes

    Lin-Zhi SHEN  

     
    LETTER-Coding Theory

      Vol:
    E102-A No:10
      Page(s):
    1416-1419

    Optical orthogonal signature pattern codes (OOSPCs) have attracted great attention due to their important application in the spatial code-division multiple-access network for image transmission. In this paper, we give a construction for OOSPCs based on cyclic codes over Fp. Applying this construction with the Reed-Solomon codes and the generalized Berlekamp-Justesen codes, we obtain two classes of asymptotically optimal OOSPCs.

  • Performance Improvement of Error-Resilient 3D DWT Video Transmission Using Invertible Codes

    Kotoku OMURA  Shoichiro YAMASAKI  Tomoko K. MATSUSHIMA  Hirokazu TANAKA  Miki HASEYAMA  

     
    PAPER-Video Coding

      Vol:
    E99-A No:12
      Page(s):
    2256-2265

    Many studies have applied the three-dimensional discrete wavelet transform (3D DWT) to video coding. It is known that corruptions of the lowest frequency sub-band (LL) coefficients of 3D DWT severely affect the visual quality of video. Recently, we proposed an error resilient 3D DWT video coding method (the conventional method) that employs dispersive grouping and an error concealment (EC). The EC scheme of our conventional method adopts a replacement technique of the lost LL coefficients. In this paper, we propose a new 3D DWT video transmission method in order to enhance error resilience. The proposed method adopts an error correction scheme using invertible codes to protect LL coefficients. We use half-rate Reed-Solomon (RS) codes as invertible codes. Additionally, to improve performance by using the effect of interleave, we adopt a new configuration scheme at the RS encoding stage. The evaluation by computer simulation compares the performance of the proposed method with that of other EC methods, and indicates the advantage of the proposed method.

  • Low Complexity Reed-Solomon Decoder Design with Pipelined Recursive Euclidean Algorithm

    Kazuhito ITO  

     
    PAPER

      Vol:
    E99-A No:12
      Page(s):
    2453-2462

    A Reed-Solomon (RS) decoder is designed based on the pipelined recursive Euclidean algorithm in the key equation solution. While the Euclidean algorithm uses less Galois multipliers than the modified Euclidean (ME) and reformulated inversionless Berlekamp-Massey (RiBM) algorithms, division between two elements in Galois field is required. By implementing the division with a multi-cycle Galois inverter and a serial Galois multiplier, the proposed key equation solver architecture achieves lower complexity than the conventional ME and RiBM based architectures. The proposed RS (255,239) decoder reduces the hardware complexity by 25.9% with 6.5% increase in decoding latency.

  • A Security Enhancement Technique for Wireless Communications Using Secret Sharing and Physical Layer Secrecy Transmission

    Shoichiro YAMASAKI  Tomoko K. MATSUSHIMA  

     
    PAPER-Network security

      Pubricized:
    2016/01/13
      Vol:
    E99-D No:4
      Page(s):
    830-838

    Secret sharing is a method of information protection for security. The information is divided into n shares and reconstructed from any k shares, but no knowledge of the information is revealed from k-1 shares. Physical layer security is a method of achieving favorable reception conditions at the destination terminal in wireless communications. In this study, we propose a security enhancement technique for wireless packet communications. The technique uses secret sharing and physical layer security to exchange a secret encryption key. The encryption key for packet information is set as the secret information in secret sharing, and the secret information is divided into n shares. Each share is located in the packet header. The base station transmits the packets to the destination terminal by using physical layer security based on precoded multi-antenna transmission. With this transmission scheme, the destination terminal can receive more than k shares without error and perfectly recover the secret information. In addition, an eavesdropper terminal can receive less than k-1 shares without error and recover no secret information. In this paper, we propose a protection technique using secret sharing based on systematic Reed-Solomon codes. The technique establishes an advantageous condition for the destination terminal to recover the secret information. The evaluation results by numerical analysis and computer simulation show the validity of the proposed technique.

  • Unique Decoding of Certain Reed-Solomon Codes

    Lin-Zhi SHEN  Fang-Wei FU  Xuan GUANG  

     
    LETTER-Coding Theory

      Vol:
    E98-A No:12
      Page(s):
    2728-2732

    In this paper, we consider the Reed-Solomon codes over Fqm with evaluations in a subfield Fq. By the “virtual extension”, we can embed these codes into homogeneous interleaved Reed-Solomon codes. Based on this property and the collaborative decoding algorithm, a new probabilistic decoding algorithm that can correct errors up to $ rac{m}{m+1}(n-k)$ for these codes is proposed. We show that whether the new decoding algorithm fails or not is only dependent on the error. We also give an upper bound on the failure probability of the new decoding algorithm for the case s=2. The new decoding algorithm has some advantages over some known decoding algorithms.

  • Cooperative Communication Using the DF Protocol in the Hierarchical Modulation

    Sung-Bok CHOI  Eui-Hak LEE  Jung-In BAIK  Young-Hwan YOU  Hyoung-Kyu SONG  

     
    LETTER-Communication Theory and Signals

      Vol:
    E98-A No:9
      Page(s):
    1990-1994

    To improve the BER performance of the conventional cooperative communication, this letter proposes an efficient method for the reliability, and it uses hierarchical modulation that has both the high priority (HP) layer and the low priority (LP) layer. To compensate more reliable transmission, the proposed method uses the error correction capability of Reed-Solomon (RS) codes additionally. The simulation results show that the proposed method can transmit data more reliably than the basic RS coded decode-and-forward (DF) method.

  • Note on Some Recent Cheater Identifiable Secret Sharing Schemes

    Rui XU  Kirill MOROZOV  Tsuyoshi TAKAGI  

     
    PAPER-Cryptography and Information Security

      Vol:
    E98-A No:8
      Page(s):
    1814-1819

    Harn and Lin proposed an algorithm to detect and identify cheaters in Shamir's secret sharing scheme in the journal Designs, Codes and Cryptography, 2009. In particular, their algorithm for cheater identification is inefficient. We point out that some of their conditions for cheater detection and identification essentially follow from those on error detection/correction of Reed-Solomon codes, which have efficient decoding algorithms, while some other presented conditions turn out to be incorrect. The extended and improved version of the above mentioned scheme was recently presented at the conference International Computer Symposium 2012 (and the journal version appeared in the journal IET Information Security). The new scheme, which is ideal (i.e. the share size is equal to that of the secret), attempts to identify cheaters from minimal number of shares (i.e. the threshold of them). We show that the proposed cheater identification is impossible using the arguments from coding theory.

  • A Low Power and Hardware Efficient Syndrome Key Equation Solver Architecture and Its Folding with Pipelining

    Kazuhito ITO  

     
    PAPER-VLSI Design Technology and CAD

      Vol:
    E98-A No:5
      Page(s):
    1058-1066

    Syndrome key equation solution is one of the important processes in the decoding of Reed-Solomon codes. This paper proposes a low power key equation solver (KES) architecture where the power consumption is reduced by decreasing the required number of multiplications without degrading the decoding throughput and latency. The proposed method employs smaller number of multipliers than a conventional low power KES architecture. The critical path in the proposed KES circuit is minimized so that the operation at a high clock frequency is possible. A low power folded KES architecture is also proposed to further reduce the hardware complexity by executing folded operations in a pipelined manner with a slight increase in decoding latency.

  • An Area-Time Efficient Key Equation Solver with Euclidean Algorithm for Reed-Solomon Decoders

    Kazuhito ITO  

     
    PAPER-VLSI Design Technology and CAD

      Vol:
    E96-A No:2
      Page(s):
    609-617

    Reed-Solomon (RS) code is one of the well-known and widely used error correction codes. Among the components of a hardware RS decoder, the key equation solver (KES) unit occupies a relatively large portion of the hardware. It is important to develop an efficient KES architecture to implement efficient RS decoders. In this paper, a novel polynomial division technique used in the Euclidean algorithm (EA) of the KES is presented which achieves the short critical path delay of one Galois multiplier and one Galois adder. Then a KES architecture with the EA is proposed which is efficient in the sense of the product of area and time.

  • Reconstruction of a Non-binary Block Code from an Intercepted Sequence with Application to Reed-Solomon Codes

    Adel ZAHEDI  Gholam-Reza MOHAMMAD-KHANI  

     
    PAPER-Sequences

      Vol:
    E95-A No:11
      Page(s):
    1873-1880

    In this paper, a method is proposed for reconstruction of the parameters of a non-binary block encoder using an intercepted sequence of noisy coded data. The proposed method is a generalization of the Barbier's method for the reconstruction of binary block codes to the more problematic case of non-binary codes. It has been shown mathematically that considering some revisions in definitions, such a generalization is possible. The proposed method is able to estimate the code parameters such as the code length, the code dimension, number of bits per symbol, and the dual-code subspace, and also to synchronize the sequence. Since the Reed-Solomon code is the most important type of non-binary block codes, an additional method is proposed to reconstruct the generator polynomial in the case of Reed-Solomon codes. The proposed method is evaluated via computer simulations which verify its strength and effectiveness.

  • An Efficient Interpolation Based Erasure-Only Decoder for High-Rate Reed-Solomon Codes

    Qian GUO  Haibin KAN  

     
    LETTER-Coding Theory

      Vol:
    E95-A No:5
      Page(s):
    978-981

    In this paper, we derive a simple formula to generate a wide-sense systematic generator matrix(we call it quasi-systematic) B for a Reed-Solomon code. This formula can be utilized to construct an efficient interpolation based erasure-only decoder with time complexity O(n2) and space complexity O(n). Specifically, the decoding algorithm requires 3kr + r2 - 2r field additions, kr + r2 + r field negations, 2kr + r2 - r + k field multiplications and kr + r field inversions. Compared to another interpolation based erasure-only decoding algorithm derived by D.J.J. Versfeld et al., our algorithm is much more efficient for high-rate Reed-Solomon codes.

  • Design and Implementation of a Low-Complexity Reed-Solomon Decoder for Optical Communication Systems

    Ming-Der SHIEH  Yung-Kuei LU  

     
    PAPER-Computer System

      Vol:
    E94-D No:8
      Page(s):
    1557-1564

    A low-complexity Reed-Solomon (RS) decoder design based on the modified Euclidean (ME) algorithm proposed by Truong is presented in this paper. Low complexity is achieved by reformulating Truong's ME algorithm using the proposed polynomial manipulation scheme so that a more compact polynomial representation can be derived. Together with the developed folding scheme and simplified boundary cell, the resulting design effectively reduces the hardware complexity while meeting the throughput requirements of optical communication systems. Experimental results demonstrate that the developed RS(255, 239) decoder, implemented in the TSMC 0.18 µm process, can operate at up to 425 MHz and achieve a throughput rate of 3.4 Gbps with a total gate count of 11,759. Compared to related works, the proposed decoder has the lowest area requirement and the smallest area-time complexity.

  • High-Speed Low-Complexity Architecture for Reed-Solomon Decoders

    Yung-Kuei LU  Ming-Der SHIEH  

     
    PAPER-Computer System

      Vol:
    E93-D No:7
      Page(s):
    1824-1831

    This paper presents a high-speed, low-complexity VLSI architecture based on the modified Euclidean (ME) algorithm for Reed-Solomon decoders. The low-complexity feature of the proposed architecture is obtained by reformulating the error locator and error evaluator polynomials to remove redundant information in the ME algorithm proposed by Truong. This increases the hardware utilization of the processing elements used to solve the key equation and reduces hardware by 30.4%. The proposed architecture retains the high-speed feature of Truong's ME algorithm with a reduced latency, achieved by changing the initial settings of the design. Analytical results show that the proposed architecture has the smallest critical path delay, latency, and area-time complexity in comparison with similar studies. An example RS(255,239) decoder design, implemented using the TSMC 0.18 µm process, can reach a throughput rate of 3 Gbps at an operating frequency of 375 MHz and with a total gate count of 27,271.

  • Performance of Adaptive Trellis Coded Modulation Applied to MC-CDMA with Bi-orthogonal Keying

    Hirokazu TANAKA  Shoichiro YAMASAKI  Miki HASEYAMA  

     
    PAPER-Communication Theory and Systems

      Vol:
    E92-A No:11
      Page(s):
    2837-2843

    A Generalized Symbol-rate-increased (GSRI) Pragmatic Adaptive Trellis Coded Modulation (ATCM) is applied to a Multi-carrier CDMA (MC-CDMA) system with bi-orthogonal keying is analyzed. The MC-CDMA considered in this paper is that the input sequence of a bi-orthogonal modulator has code selection bit sequence and sign bit sequence. In, an efficient error correction code using Reed-Solomon (RS) code for the code selection bit sequence has been proposed. However, since BPSK is employed for the sign bit modulation, no error correction code is applied to it. In order to realize a high speed wireless system, a multi-level modulation scheme (e.g. MPSK, MQAM, etc.) is desired. In this paper, we investigate the performance of the MC-CDMA with bi-orthogonal keying employing GSRI ATCM. GSRI TC-MPSK can arbitrarily set the bandwidth expansion ratio keeping higher coding gain than the conventional pragmatic TCM scheme. By changing the modulation scheme and the bandwidth expansion ratio (coding rate), this scheme can optimize the performance according to the channel conditions. The performance evaluations by simulations on an AWGN channel and multi-path fading channels are presented. It is shown that the proposed scheme has remarkable throughput performance than that of the conventional scheme.

  • Performance of Reed-Solomon Coded MC-DS-CDMA with Bi-orthogonal Modulation

    Hirokazu TANAKA  Kyung Woon JANG  Shoichiro YAMASAKI  Miki HASEYAMA  

     
    PAPER-Spread Spectrum Technologies and Applications

      Vol:
    E92-A No:10
      Page(s):
    2600-2608

    In this paper, an error correction scheme suitable for MC-DS-CDMA system with bi-orthogonal modulation is proposed. The input sequence of a bi-orthogonal modulator consists of n - 1 bit code selection bit sequence and 1 bit sign bit sequence. In order to apply an efficient error correction code, the following points should be considered; (1) if the code selection bits can be protected sufficiently, the sign bit error can also be reduced sufficiently, (2) since a code selection bit sequence consists of n - 1 bits, employing a symbol error correcting code is more effective for encoding code selection bits, (3) the complexity of the error correction encoder and decoder implementations should be minimum. Based on these conditions, we propose to employ Reed-Solomon (RS) code for encoding the code selection bits and no error correction code for the sign bit. Additionally, detection algorithm at the bi-orthogonal demodulator is modified for compensating degradations of the sign bit error rate performance. The performance in an Additive White Gaussian Noise (AWGN) channel is evaluated by both theoretical analysis and computer simulations. The performance evaluations by simulations on multi-path fading channels are also shown. It is shown that the proposed scheme has remarkable improvement.

  • A Partition Decoding for Reed-Solomon Codes Based on Partial Bit Reliability

    Ta-Hsiang HU  Ming-Hua CHANG  Ing-Jiunn SU  

     
    PAPER-Fundamental Theories for Communications

      Vol:
    E90-B No:10
      Page(s):
    2784-2792

    This study presents a partition decoding algorithm for an (mN, mK) binary image of an (N, K) Reed Solomon code over GF(2m). A proposed partition decoding algorithm includes several steps. Firstly we compute m's segmental reliability values of a received subvector of length N and determine which one with the least segmental reliability value. A permutation is performed on a binary generator matrix of an RS code and a received vector, which are then partitioned into two submatrices and two subvectors. The first subvector of length N(m-1) associate with the first submatrix and the second subvector with the least segmental reliability value relates to the second submatrix. Secondly, an MLD algorithm based on the first submatrix is employed to decode the first subvector. Thirdly, an MLD algorithm based on a BCH generator matrix is employed to decode the second subvector. A codeword is finally outputted after performing the inverse permutation on a concatenation of code vectors decoded from these two decoding. The error coefficient and minimum Hamming distance of the code sequences generated in the first submatrix are fewer than those of a corresponding binary image. Simulation results show that at low and medium SNRs, the effect of error coefficient becomes more significant than that of minimum Hamming distance. Minimum Hamming distances and error coefficients of code sequences generated in the first submatrices and their corresponding binary images have been explored in this work. For (60,36,7)RS(b), (155,125,7)RS(b), (155,105,11)RS(b) and (889, 847,7))RS(b) being binary images of (15,9,7)RS, (31,25,7)RS, (31,21,11)RS and (127,121,7)RS codes respectively, with BPSK signaling over AWGN channels, the decoding performances of proposed partition decoding algorithm are a little poorer than those of MLD [10] by 1.0 to 1.4 dB at BER 10-5, but better than those of GMD decoding by [1] 0.8 to 1.1 dB. For SNR of 5 dB, proposed partition decoding algorithm only takes 50% to 60% amount of bit operations of an MLD [10]. Under a constraint of decoding complexity, proposed partition decoding algorithm may be a solution to decode binary images of long RS codes, which provides superior performance to GMD decoding with much lower complexity than an MLD.

  • A VLSI Design of a Pipelining and Area-Efficient Reed-Solomon Decoder

    Wei-min WANG  Du-yan BI  Xing-min DU  Lin-hua MA  

     
    LETTER-VLSI Systems

      Vol:
    E90-D No:8
      Page(s):
    1301-1303

    A novel high-speed and area-efficient Reed-Solomon decoder is proposed, which employs pipelining architecture of minimized modified Euclid (ME) algorithm. The logic synthesis and simulation results of its VLSI implementation show that it not only can operate at a higher clock frequency, but also consumes fewer hardware resources.

1-20hit(45hit)